package com.boomsecret.algorithm;

import java.util.Objects;

/**
 * Created by wangjinliang on 2018/4/26.
 */
public class QuickSortDemo {
    public static void main(String[] args) {
        int[] array = {9, 6, 7, 6, 5, 4, 3, 2, 6, 0};
        printArray(array);
        quickSort(array);
        printArray(array);
    }

    private static void quickSort(int[] array) {
        if (Objects.isNull(array) || array.length == 1) {
            return;
        }
        arrayPartQuickSort(array, 0, array.length - 1, 0);
    }

    private static void arrayPartQuickSort(int[] array, int startIndex, int endIndex, int baseIndex) {
        if (endIndex - startIndex < 1) {
            return;
        }
        int tempStartIndex = startIndex;
        int tempEndIndex = endIndex;
        int tempBaseValue = array[baseIndex];
        int tempStartValue;
        int tempEndValue;
        while (true) {
            while(true) {
                tempEndValue = array[tempEndIndex];
                if (tempEndValue < tempBaseValue) {
                    break;
                }
                if (tempEndIndex > tempStartIndex) {
                    tempEndIndex --;
                } else {
                    break;
                }
            }
            while(true) {
                tempStartValue = array[tempStartIndex];
                if (tempStartValue > tempBaseValue) {
                    break;
                }
                if (tempStartIndex < tempEndIndex) {
                    tempStartIndex ++;
                } else {
                    break;
                }
            }
            if (tempStartIndex == tempEndIndex) {
                break;
            }
            int swapValueTemp = array[tempEndIndex];
            array[tempEndIndex] = array[tempStartIndex];
            array[tempStartIndex] = swapValueTemp;
        }
        int swapValueTemp = array[baseIndex];
        array[baseIndex] = array[tempEndIndex];
        array[tempEndIndex] = swapValueTemp;
        arrayPartQuickSort(array, startIndex, tempEndIndex - 1, startIndex);
        arrayPartQuickSort(array, tempEndIndex + 1, endIndex, tempEndIndex + 1);
    }

    private static void printArray(int[] array) {
        if (Objects.isNull(array)) {
            System.out.println(array);
        }
        for (int item : array) {
            System.out.print(item + " ");
        }
        System.out.println();
    }
}